package Review.HashSet;

import java.util.*;

public class Test1 {



    public boolean isAnagram(String a, String b) {
        int[] record=new int[26];
        for(int i=0;i<a.length();i++){
            record[a.charAt(i)-'a']++;
        }
        for(int i=0;i<b.length();i++){
            record[b.charAt(i)-'a']--;
        }
        for(int count:record){
            if(count!=0){
                return false;
            }
        }
        return true;
    }
    //连个数组的交集
    public int[] interssection(int[] num1,int[] num2){
        if(num1==null||num1.length==0||num2==null||num2.length==0){
            return null;
        }
        Set<Integer> set1=new HashSet<>();
        Set<Integer> set2=new HashSet<>();
        for(int i:num1){
            set1.add(i);
        }
        //存在去重操作
        for(int i:num2){
            if(set1.contains(i)){
                set2.add(i);
            }
        }
        //将方法转为数组
        int[] arr=new int[set2.size()];
        int j=0;
        for(int i:set2){
            arr[j++]=i;
        }
        return arr;
    }
    public boolean isHappy(int n){
        Set<Integer> record=new HashSet<>();
        //添加到record里面是为了保证，不存在是循环
        while(n!=1&&!record.contains(n)){
            record.add(n);
            n=getNextNumber(n);
        }
        //跳出循环看是否符合条件
        return n==1;
    }
    private int getNextNumber(int n){
        int res=0;
        while(n>0){
            int temp=n%10;
            res+=temp*temp;
            n=n/10;
        }
        return res;
    }
    public int[] twoSum(int[] nums, int target) {
        int[] res=new int[2];
        if(nums==null||nums.length==0){
            return null;
        }
        Map<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<nums.length;i++){
            //目标值
            int temp=target-nums[i];
            if(map.containsKey(temp)){
                //含有的话就赋值
                res[1]=i;
                res[0]=map.get(temp);
                break;
            }
            //如果不含有，就添加里面
            map.put(nums[i],i);
        }
     return res;
    }
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int res=0;
        Map<Integer,Integer> map=new HashMap<>();
        for(int i:nums1){
            for(int j:nums2){
                int sum=i+j;
                //统计该和出现的次数，+1只加的本次
                map.put(sum,map.getOrDefault(sum,0)+1);
            }
        }
        for(int i:nums3){
            for(int j:nums4){
                res+=map.getOrDefault(0-i-j,0);
            }

        }
        return res;
    }
    public boolean canConstruct(String s1,String s2) {
        if(s1.length()>s2.length()){
            return false;
        }
        //定义哈希映射数组
        int[] record=new int[26];
        for(char c:s1.toCharArray()){
            record[c-'a']+=1;
        }
        for(char c:s2.toCharArray()){
            record[c-'a']-=1;
        }
        for(int i:record){
            if(i<0){
                //说明前者比后者多字母
                return false;
            }
        }
        return true;
    }
    public List<List<Integer>> findThreeSums(int[] num){
        List<List<Integer>> list=new ArrayList<>();
        Arrays.sort(num);
        for(int i=0;i<num.length;i++){
            if(num[i]>0){
                return list;
            }
            if(i>0&&num[i]==num[i-1]){
                //进行去重
                continue;
            }
            int left=i+1;
            int right=num.length-1;
            while(left<right){
                int sum=num[i]+num[left]+num[right];
                if(sum>0){
                    right--;
                }
                else if(sum<0){
                    left++;
                }
                else{
                    //临时创建新的集合
                    list.add(Arrays.asList(num[i],num[left],num[right]));
                    //去重逻辑
                    while(right>left&&num[right]==num[right-1]){
                        right--;
                    }
                    while(left<right&&num[left]==num[left+1]){
                        left++;
                    }
                    right--;
                    left++;
                }
            }
        }
        return list;
    }
    public List<List<Integer>> fourSum(int[] num,int target){
        Arrays.sort(num);
        List<List<Integer>> list=new ArrayList<>();
        for(int k=0;k<num.length;k++){
            //进行剪枝
            if(num[k]>target&&num[k]>=0){
                break;
            }
            //去重
            if(k>0&&num[k]==num[k-1]){
                continue;
            }
            for(int i=k+1;i<num.length;i++){
                //剪纸操作
                if(num[k]+num[i]>target&&num[k]+num[i]>=0){
                    break;
                }
                if(i>k+1&&num[i]==num[i-1]){
                    continue;
                }
                int left=i+1;
                int right=num.length-1;
                while(right>left){
                    long sum=(long)num[i]+num[left]+num[right]+num[k];
                    if(sum>target){
                        right--;
                    }
                    else if(sum<target){
                        left++;
                    }
                    else{
                        list.add(Arrays.asList(num[i],num[left],num[right],num[k]));
                        //组合后进行去重操作
                        while(right>left&&num[right]==num[right-1]){
                            right--;
                        }
                        while(left<right&&num[left]==num[left+1]){
                            left++;
                        }
                        right--;
                        left++;
                    }
                }
            }
        }
        return list;
    }
}
